package com.LC._51;

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<List<String>>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);//
        Set<Integer> columns = new HashSet<Integer>(); //
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);//构造棋盘
            solutions.add(board);
        } else {
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {//保存皇后所在列
                    continue;//结束本次循环
                }
                int diagonal1 = row - i;//判断是否在对角线==看横坐标-纵坐标的值是否唯一

                if (diagonals1.contains(diagonal1)) {//是否在同一对角线
                    continue;//结束本次循环
                }
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {//是否在同一对角线
                    continue;//结束本次循环
                }
                queens[row] = i;//记录皇后在每一行的什么位置
                columns.add(i);//记录皇后在的列数
                diagonals1.add(diagonal1);//横坐标-纵坐标的值
                diagonals2.add(diagonal2);//横坐标+纵坐标的值
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q'; //保存每一层所有个体的数据
            board.add(new String(row));////保存所有层级的数据
        }
        return board;
    }

    public static void main(String[] args) {
        Solution s=new Solution();
        System.out.println(s.solveNQueens(2));
    }
}
//public class Solution {
//
//    // 八皇后问题，在一个8×8的国际象棋棋盘上摆放8个皇后，摆放需遵守皇后不能处于同一行、同一列、同一斜线上，问有多少种摆法
//    int max = 8;//皇后个数
//    static  int count = 0;//记录有多少种摆法
//    // 初始化一个数组用于存放结果
//    /*
//     * 这里用一维数组存放数据就可以了，这里一维数组中的值存放的是皇后的列坐标，
//     * 因为规定皇后是不能摆放在同一行，所以每一行只有一个皇后 ； 一维数组 arr
//     * 的第一个值就是 棋盘第一行皇后的列坐标值，第二个值就是皇后在棋盘第二行的列坐标值
//     */
//    int[] arr = new int[max];
//
//    public static void main(String[] args) {
//        // TODO Auto-generated method stub
//
//        Solution quuen = new Solution();
//        quuen.PutQuuen(0);
//        System.out.println("共有"+count+"种摆法");
//    }
//
//    //写一个摆皇后的方法
//    private void PutQuuen(int n) {
//        if(n==max) {//因为n是从0开始增加，即n=0表示放第一个皇后，当n==max时表示皇后已经摆完了
//            Print();
//            return;
//        }
//        for(int i=0;i<max;i++) {
//            arr[n]=i;//放置第一个皇后
//            if(judge(n)) {//判断皇后的位置是否冲突，不冲突继续放下一个皇后
//                PutQuuen(n+1);
//            }
//        }
//    }
//
//
//    // 写一个方法，判断皇后在该位置是否会引起冲突，即在同一行或同一列或同一斜线
//    private boolean judge(int n) {
//        for (int i = 0; i < n; i++) {
//
//            /*
//             * 1. 判断 皇后是否在同一列，只需判断皇后的列坐标是否相等即可，即arr[i] == arr[n]
//             * 2.判断皇后是否在同一斜线上，只需判断两个皇后的列坐标之差的绝对值与其横坐标之差的绝对值是否相等即可，
//             *   即Math.abs(n - i) == Math.abs(arr[i] - arr[n])
//             *  */
//            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[i] - arr[n])) {
//                return false;//违反了规则，返回false
//            }
//        }
//        return true;
//    }
//
//    //输出
//    private void Print() {
//        // TODO Auto-generated method stub
//        for(int i=0;i<arr.length;i++) {
//            System.out.print(arr[i] + " ");
//        }
//        count++;
//        System.out.println();
//    }
//
//}
